package test230606;

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/6 0:43
 * 376. 摆动序列
 * https://leetcode.cn/problems/wiggle-subsequence/
 */
public class Solution02 {

    // my 动态规划 思路
    public int wiggleMaxLength(int[] nums) {
        // 边界处理
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] f = new int[n];  // f[i] 表示以 nums[i] 结尾且最后状态为 “上升” 的所有子序列的最大长度
        int[] g = new int[n];  // g[i] 表示以 nums[i] 结尾且最后状态为 “下降” 的所有子序列的最大长度
        // 初始化状态量, 极端的最小长度为 1
        Arrays.fill(f, 1);
        Arrays.fill(g, 1);
        // 动态规划过程
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j <= i - 1; ++j) {
                if (nums[i] > nums[j]) {
                    // 上升状态
                    f[i] = Math.max(f[i], g[j] + 1);
                } else if (nums[i] < nums[j]) {
                    // 下降状态
                    g[i] = Math.max(g[i], f[j] + 1);
                }
            }
        }
        // 统计最大长度
        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            if (f[i] > maxLen) {
                maxLen = f[i];
            }
            if (g[i] > maxLen) {
                maxLen = g[i];
            }
        }
        return maxLen;
    }
}
